package com.sheng.leetcode.year2022.month12.day07;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/12/07
 * <p>
 * 1775. 通过最少操作次数使数组的和相等<p>
 * <p>
 * 给你两个长度可能不等的整数数组nums1 和nums2。两个数组中的所有值都在1到6之间（包含1和6）。<p>
 * 每次操作中，你可以选择 任意数组中的任意一个整数，将它变成 1到 6之间 任意的值（包含 1和 6）。<p>
 * 请你返回使 nums1中所有数的和与nums2中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]<p>
 * 输出：3<p>
 * 解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。<p>
 * - 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。<p>
 * - 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。<p>
 * - 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]<p>
 * 输出：-1<p>
 * 解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums1 = [6,6], nums2 = [1]<p>
 * 输出：3<p>
 * 解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。<p>
 * - 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。<p>
 * - 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。<p>
 * - 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums1.length, nums2.length <= 10^5<p>
 * 1 <= nums1[i], nums2[i] <= 6<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations">1775. 通过最少操作次数使数组的和相等</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1775 {

    @Test
    public void test01() {
//        int[] nums1 = {1, 2, 3, 4, 5, 6}, nums2 = {1, 1, 2, 2, 2, 2};
//        int[] nums1 = {1,1,1,1,1,1,1}, nums2 = {6};
        int[] nums1 = {6, 6}, nums2 = {1};
        System.out.println(new Solution().minOperations(nums1, nums2));
    }
}

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int sum1 = Arrays.stream(nums1).sum();
        int sum2 = Arrays.stream(nums2).sum();
        // 相等直接返回
        if (sum1 == sum2) {
            return 0;
        }
        // 保证 sum1 <= sum2
        if (sum1 > sum2) {
            return minOperations(nums2, nums1);
        }
        // 差值
        int diff = sum2 - sum1;
        int[] arr = new int[length1 + length2];
        int k = 0;
        // 总和小的计算和 6 之间的差值，获取数组内每个元素还能加几达到上限
        for (int v : nums1) {
            arr[k++] = 6 - v;
        }
        // 总和大的计算和 1 之间的差值，获取每个元素还能减几达到下线
        for (int v : nums2) {
            arr[k++] = v - 1;
        }
        // 排序
        Arrays.sort(arr);
        // 循环
        for (int i = 1, j = arr.length - 1; j >= 0; ++i, --j) {
            // 当差值小余等于 0 时代表两个数组此时可以达到相等的状态
            diff -= arr[j];
            if (diff <= 0) {
                return i;
            }
        }
        // 否则无法相等，返回 -1
        return -1;
    }
}
